# 对10个数进行排序

# 排序算法 内置函数 冒泡排序 选择排序 插入排序 归并排序 快速排序

# 内置函数 sort
lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
lis.sort()
print(lis)

# 内置函数 sorted
lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(sorted(lis))

# 使用冒泡排序
def bubbleSort(list, reverse=False):
    l = len(list)
    # 外层 - 记录当前轮次-1
    for i in range(l):
        # 内层 - 取得当前用与比较判断的前一个元素的list中的下标
        for j in range(l-i-1):
            if not reverse:
                if list[j] > list[j+1]:
                    list[j], list[j+1] = list[j+1], list[j]
            else:
                if list[j] < list[j+1]:
                    list[j], list[j+1] = list[j+1], list[j]
                
    return list

lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(bubbleSort(lis))

# 插入排序
def insertionSort(list, reverse=False):
    l = len(list)
    # 外层循环，设置循环插入的次数，默认原本下标为0的元素不需要被取值比较，只需要被其他元素比较。
    for i in range(1, l):
        # 内层循环，拿着当前的list[i]元素，从list[0]开始，向list[i]原本位置，比较，看看中间哪个位置适合它。
        for j in range(i):
            if list[i] < list[j]:
                temp = list.pop(i)
                list.insert(j, temp)
                break
    return list

lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(insertionSort(lis))


# 选择排序
def selectionSort(list, reverse=False):
    l = len(list)
    # 外层循环，当前排序到的下标位置
    for i in range(l-1):
        # 内层循环，遍历其后的所有元素下标，看看哪个最适合放在下标i位置，并获取目标下标（target）
        target = i
        for j in range(i, l):
            if not reverse:
                if list[target] > list[j]:
                    target = j
            else:
                if list[target] < list[j]:
                    target = j
                
        # 循环结束后，我们将获得当前后面所有数据中，最适合当前i位置的数据位置
        # 交换数据
        list[i], list[target] = list[target], list[i]
    return list
    
lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(selectionSort(lis))


# 归并排序
def mergeSort(list):
    l = len(list)
    if l <= 1:
        return list
    if l == 2:
        if list[0] > list[1]:
            list[0], list[1] = list[1], list[0]
        return list
    m = l // 2
    #print(l, m)
    list1 = mergeSort(list[:m])
    list2 = mergeSort(list[m:])
    list = []
    while True:
        #print(f'{list1} {list2}')
        if not list1:
            list += list2
            break
        if not list2:
            list += list1
            break
        if list1[0] > list2[0]:
            list.append(list2[0])
            list2.pop(0)
        else:
            list.append(list1[0])
            list1.pop(0)
    return list
        
lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(mergeSort(lis))


# 快速排序
def quickSort(arr):
    l = len(arr)
    if l <= 1:
        return arr

    pivot = arr[l // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quickSort(left) + middle + quickSort(right)


lis = [3, 23, 12, 30, 90, 93, 23, 39, 1, 5]
print(quickSort(lis))
